﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
using PPClasses;

namespace PortalPlan.Solvers
{
    class DFS : Solver
    {
        public DFS(List<Portal> points) 
            : base(points)
        {
        }

        public override bool CanThread
        {
            get { return false; }
        }

        public override void GoGoGo()
        {
            List<Pair> path = new List<Pair>();

            SearchLevel(new SearchWork(0, 0, PairChoices, path));
            WaitAllThreads();
            CompletelyDone = true;
        }

        private class SearchWork
        {
            public int level;
            public int prevlevelstep;
            public List<Pair> choices;
            public List<Pair> path;

            public SearchWork(int lev, int pls, List<Pair> ch, List<Pair> pa)
            {
                level = lev;
                prevlevelstep = pls;
                choices = ch;
                path = pa;
            }
        }

        private void SearchLevel(object swo)
        {
            SearchWork sw = swo as SearchWork;
            System.Diagnostics.Debug.Assert(sw != null);
            if (sw == null)
                return;

            // at each level:
            //  - for each choice of link
            //   - skip 0 to n choices
            //   - take the n+1'th choice
            //   - remove any blocked links from the remaining choices
            //   - pass onto the next level
            //  - when no more choices, evaluate path

            if (sw.choices.Count != 0)
            {
                for (int i = 0; i <= sw.choices.Count - 1; i++)
                {
                    if (Stop)
                    {
                        return;
                    }
                    if (sw.level == 0)
                        PercentDone = 100.0 * i / (sw.choices.Count - 1);
                    List<Pair> choiceCopy = new List<Pair>(sw.choices);
                    List<Pair> pathCopy = new List<Pair>(sw.path);
                    if (i > 0)
                        choiceCopy.RemoveRange(0, i); // remove the first i elements
                    Pair addPair = choiceCopy[0];
                    pathCopy.Add(addPair);
                    choiceCopy.RemoveAt(0); // choice taken, so remove it too
                    foreach (Pair blocked in ChoicesBlock[addPair])
                        choiceCopy.Remove(blocked); // remove links that addPair blocks

                    SearchWork sw2 = new SearchWork(sw.level + 1, i, choiceCopy, pathCopy);
                    if (sw.level == 0)
                        StartNextAvailableThread(sw2);
                    else
                        SearchLevel(sw2);
                }
            }
            else
            {
                // this is the end of this path
                //System.Diagnostics.Debug.Print("DFS: "+ DumpPath(path));

                List<Pair> solution = new List<Pair>(MustLink); // start with these
                solution.AddRange(sw.path);
                EvaluateSolution(solution);
            }
        }

        private Thread[] T;

        private void WaitAllThreads()
        {
            if (T == null)
                return;

            System.Diagnostics.Debug.Print("Waiting for all DFS threads to stop...");
            while (true)
            {
                bool allIdle = true;
                for (int i = 0; i < T.Length; i++)
                {
                    if (T[i] == null || T[i].ThreadState == ThreadState.Stopped)
                        continue;
                    allIdle = false;
                    break;
                }
                if (allIdle)
                    return;
                Thread.Sleep(500);
            }
        }


        private void StartNextAvailableThread(SearchWork sw2)
        {
            if (T == null)
            {
                T = new Thread[Environment.ProcessorCount];
            }

            while (true)
            {
                for (int i = 0; i < T.Length; i++)
                {
                    if (T[i] == null || T[i].ThreadState == ThreadState.Stopped)
                    {
                        T[i] = new Thread(new ParameterizedThreadStart(SearchLevel))
                        {
                            Name = "DFS Thread " + (i + 1) + " (" + sw2.prevlevelstep + ")",
                            IsBackground = true
                        };
                        T[i].Start(sw2);
                        return;
                    }
                }
                Thread.Sleep(100);
            }
        }

        public override string StatusText()
        {
            return "DFS: " + base.StatusText();
        }
    }

}
